#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;


//int main() {
//    string arr;
//    cin >> arr;
//    int num = arr.size();
//    long c = 0;
//    long ch = 0;
//    long chn = 0;
//    for (int i = 0; i < num; i++)
//    {
//        if (arr[i] == 'C')
//        {
//            c++;
//        }
//        else if (arr[i] == 'H')
//        {
//            ch += c;
//        }
//        else if (arr[i] == 'N')
//        {
//            chn += ch;
//        }
//    }
//    cout << chn << endl;
//}

//class Max
//{
//public:
//	int m_Max(int a, int b, int c)
//	{
//		int max = a > b ? a : b;
//		max = max > c ? max : c;
//		return max;
//	}
//};
//int main()
//{
//	int a, b, c;
//	Max m;
//	cin >> a >> b >> c;
//	int max = m.m_Max(a, b, c);
//	cout << max << endl;
//	system("pause");
//	return 0;
//}

//int main()
//{
//	int x, y;
//	cin >> x >> y;
//	int arr[100] = { 0 };
//	for (int i = 0; i < x * y; i++)
//	{
//		cin >> arr[i];
//		if ((i + 1) % y == 0 && i != 0)
//		{
//			cout << arr[i] << endl;
//		}
//		else
//		{
//			cout << arr[i] << " ";
//		}
//	}
//	system("pause");
//	return 0;
//}

//int main()
//{
//	int x, y;
//	cin >> x >> y;
//	int arr[10][10] = {0};
//	int max = 0;
//	int x1 = 0, y1 = 0;
//	for (int i = 1; i <= x ; i++)
//	{
//		for (int n = 1; n <= y; n++)
//		{
//			cin >> arr[i][n];
//			if (max < arr[i][n])
//			{
//				x1 = i;
//				y1 = n;
//				max = arr[i][n];
//			}
//		}
//	}
//	cout << x1 << " " << y1 << endl;
//	system("pause");
//	return 0;
//}

//int main()
//{
//	int n;
//	cin >> n;
//	int arr[10][10] = { 0 };
//	for (int x = 0; x < n; x++)
//	{
//		for (int y = 0; y < n; y++)
//		{
//			cin >> arr[x][y];
//		}
//	}
//	for (int x = 0; x < n; x++)
//	{
//		for (int y = 0; y < n; y++)
//		{
//			if (x>y&&arr[x][y]!=0)
//			{
//				cout << "NO" << endl;
//				system("pause");
//				return 0;
//			}
//		}
//	}
//	cout << "YES" << endl;
//	system("pause");
//	return 0;
//}

//int main()
//{
//	int m, n;
//	int x, y;
//	cin >> m >> n;
//	int arr[10][10] = { 0 };
//	for (x = 0; x < m; x++)
//	{
//		for (y = 0; y < n; y++)
//		{
//			cin >> arr[x][y];
//		}
//	}
//	for (x = 0; x < n; x++)
//	{
//		for (y = 0; y < m; y++)
//		{
//			cout << arr[y][x] << " ";
//		}
//		cout << endl;
//	}
//	system("pause");
//	return 0;
//}

//int main()
//{
//	int m, n;
//	int x, y;
//	cin >> m >> n;
//	int arr[10][10] = { 0 };
//	for (x = 0; x < m; x++)
//	{
//		for (y = 0; y < n; y++)
//		{
//			cin >> arr[x][y];
//		}
//	}
//	int k = 0;
//	cin >> k;
//	while (k--)
//	{
//		char num;
//		int a, b;
//		cin >> num >> a >> b;
//		if (num == 'c')
//		{
//			for (x = 0; x < m; x++)
//			{
//				int k = arr[x][a-1];
//				arr[x][a-1] = arr[x][b-1];
//				arr[x][b-1] = k;
//			}
//		}
//		else if (num == 'r')
//		{
//			for (y = 0; y < n; y++)
//			{
//				int k = arr[b-1][y];
//				arr[b-1][y] = arr[a-1][y];
//				arr[a-1][y] = k;
//			}
//		}
//	}
//	for (x = 0; x < m; x++)
//	{
//		for (y = 0; y < n; y++)
//		{
//			cout << arr[x][y] << " ";
//		}
//		cout << endl;
//	}
//	system("pause");
//	return 0;
//}

//int main()
//{
//	int k;
//	cin >> k;
//	int arr[30][30] = { 0 };
//	for (int i = 0; i < k; i++)
//	{
//		for (int n = 0; n <= i; n++)
//		{
//			if (n == i || n == 0)
//			{
//				arr[i][n] = 1;
//			}
//			else
//			{
//				arr[i][n] = arr[i - 1][n] + arr[i - 1][n - 1];
//			}
//		}
//		cout << endl;
//	}
//	for (int i = 0; i < k; i++)
//	{
//		for (int n = 0; n <= i; n++)
//		{
//			cout << arr[i][n] << " ";
//		}
//		cout << endl;
//	}
//	system("pause");
//	return 0;
//}